package com.mashibing.class08;

/**
 * @Auther: huangxiaode
 * @Date: 2024-02-02 - 02 - 02 - 14:37
 * @Description: com.mashibing.class08
 * @version: 1.0
 */
public class Code02_MergeSort {
    // 递归方法实现
    public static void mergeSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    // arr[L...R]范围上，请让这个范围上的数，有序！
    public static void process(int[] arr, int L, int R) {
        // 只有一个数的时候 就是已经有序了, 不需要再排序了.
        if (L == R) {
            return;
        }
        // int mid = (L + R) / 2
        int mid = L + ((R - L) >> 1);
        // 对左半部分的数据进行排序
        process(arr, L, mid);
        // 对右半部分数据进行排序
        process(arr, mid + 1, R);
        // 左右半部分合并
        merge(arr, L, mid, R);
    }

    /**
     * @param arr
     * @param L 左边界索引
     * @param M 中间节点索引
     * @param R 右边界索引
     */
    public static void merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1]; // L到 R上有几个数 就准备多长.
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        while (p1 <= M && p2 <= R) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 要么p1越界，要么p2越界
        // 不可能出现：共同越界
        while (p1 <= M) { // p1 没有越界, 把p1剩下的数据拷贝到help中去.
            help[i++] = arr[p1++];
        }
        while (p2 <= R) { // p2 没有越界, 把p2剩下的数据拷贝到help中去.
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
    }

    public static void mergeSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int step = 1;
        int N = arr.length;
        while (step < N) { // 步长小于或者等于总长度的时, while循环继续.
            int L = 0; // L 从 0 开始
            while (L < N) {
                // 计算中点坐标.
                int M = 0;
                // 从长度推算step是否够不够?
                if (N-L>=step){
                    M = L + step -1;
                }else {
                    M = N-1;
                }
                if (M==N-1){ // 说明没有有组, 直接break.
                    break;
                }
                // 计算右边界点的坐标
                int R = 0;
                // N-1-(M+1)+1 = N- 1 - M
                if (N - 1 - M >= step) {
                    R = M + step;
                } else {
                    R = N - 1;
                }
                // 归并排序 L...M, M+1...R
                merge(arr, L, M, R);
                // L节点右移.
                if (R == N - 1) { // 右边界数据没有了
                    break;
                } else { // 右边界数据有的话, 则 左边界移动到右边界后面一个节点作为下一个左节点
                    L = R + 1;
                }
            }
            if (step > N / 2) {
                break;
            }
            step *= 2; // 每次让step乘以2.
        }

    }

    // 非递归方法实现
//	public static void mergeSort2(int[] arr) {
//		if (arr == null || arr.length < 2) {
//			return;
//		}
//		int N = arr.length;
//		int mergeSize = 1;
//		while (mergeSize < N) {
//			int L = 0;
//			while (L < N) {
//				if (mergeSize >= N - L) {
//					break;
//				}
//				int M = L + mergeSize - 1;
//				int R = M + Math.min(mergeSize, N - M - 1);
//				merge(arr, L, M, R);
//				L = R + 1;
//			}
//			if (mergeSize > N / 2) {
//				break;
//			}
//			mergeSize <<= 1;
//		}
//	}

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            mergeSort1(arr1);
            mergeSort2(arr2);
            if (!isEqual(arr1, arr2)) {
                System.out.println("出错了！");
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println("测试结束");
    }

}
